package recursive;

import java.util.ArrayList;
import java.util.List;

/**
 * 子集问题
 * https://leetcode-cn.com/problems/subsets/
 * 给定一个由不同数字组成的数组，返回该数组的子集
 * 解题思路：针对数组中的每一个元素，都有两种情况：加入子集和不加入子集
 * 注意：1、确定递归边界——nums遍历完成
 *      2、保护与还原现场——加进共享变量中的数据，在使用完后要记得删除
 *      3、List 中的 add 方法是浅复制
 *      4、List 中的 remove 方法入参是下标，注意 i 不是共享变量实际的长度
 * 测试案例：1、{1,2}
 *         2、{1,2,3}
 *         3、{0}
 */
public class Subsets {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        perform(nums, 0);
        return result;
    }

    private void perform(int[] nums, int i){
        if (i >= nums.length){
            List<Integer> r = new ArrayList<>(); // 深复制结果
            r.addAll(res);
            result.add(r);
            return;
        }

        perform(nums, i + 1); // 不加入子集，继续递归
        res.add(nums[i]); // 加入子集
        perform(nums, i + 1);
        res.remove(res.size()-1); // 还原到上一步状态
    }
}
